package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 不同的子序列
    static class Solution {
        public int numDistinct(String _s, String _t) {
            // 1) 边界处理和初始化
            int n = _s.length();
            int m = _t.length();
            char[] s = _s.toCharArray();
            char[] t = _t.toCharArray();

            // 2) 创建 DP 表：dp[i][j] 表示 s[0..i-1] 中组成 t[0..j-1] 的方案数
            int[][] dp = new int[n + 1][m + 1];

            // 3) 初始化：任意长度的s都能组成空串t
            for (int i = 0; i <= n; i++) {
                dp[i][0] = 1;
            }

            // 4) 动态规划填表
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (s[i - 1] == t[j - 1]) {
                        // 字符匹配：可选择使用或不使用当前字符
                        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                    } else {
                        // 字符不匹配：只能跳过s的当前字符
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }

            // 5) 返回结果
            return dp[n][m];
        }
    }
}